//给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 
//
// 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串： 
//
// 
// s = s1 + s2 + ... + sn 
// t = t1 + t2 + ... + tm 
// |n - m| <= 1 
// 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ... 
// 
//
// 注意：a + b 意味着字符串 a 和 b 连接。 
//
// 
//
// 示例 1： 
// 
// 
//输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：s1 = "", s2 = "", s3 = ""
//输出：true
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s1.length, s2.length <= 100 
// 0 <= s3.length <= 200 
// s1、s2、和 s3 都由小写英文字母组成 
// 
//
// 
//
// 进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它? 
//
// Related Topics 字符串 动态规划 👍 1062 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-01-03 14:24:37
 * @description 97.交错字符串
 
 */
 
public class InterleavingString {
    public static void main(String[] args) {
    //测试代码
    InterleavingString fun = new InterleavingString();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isInterleave1(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        int t = s3.length();
        if(m+n!=t) return false;
        boolean [][] dp=new boolean[m+1][n+1];
        dp[0][0]=true;
        for (int i = 0; i <=m; i++) {
            for (int j = 0; j <=n; j++) {
                int p=i+j-1;
                if(i>0){
                    dp[i][j]=dp[i][j]||(dp[i-1][j]&&s3.charAt(p)==s1.charAt(i-1));
                }
                if(j>0){
                    dp[i][j]=dp[i][j]||(dp[i][j-1]&&s3.charAt(p)==s2.charAt(j-1));
                }
            }
        }
        return dp[m][n];
    }
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        int t = s3.length();
        if(m+n!=t) return false;
        boolean [] dp=new boolean[n+1];
        dp[0]=true;
        for (int i = 0; i <=m; i++) {
            for (int j = 0; j <=n; j++) {
                int p=i+j-1;
                if(i>0){
                    dp[j]=(dp[j]&&s3.charAt(p)==s1.charAt(i-1));
                }
                if(j>0){
                    dp[j]=dp[j]||(dp[j-1]&&s3.charAt(p)==s2.charAt(j-1));
                }
            }
        }
        return dp[n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
